package com.cn.algorithm02.class12;

import java.util.ArrayList;
import java.util.List;

/***
 * @author: hels
 * @description: 多叉树与二叉树相互转换
 * 多叉树X所有的叶子节点，转换二叉树过程：X左叶子节点的右边界
 *        X                            X
 *    (a      b     c)      ==>      a
 *  (d e f)                       d      b
 *                                   e      c
 *                                      f
 *    多叉树结构如下：
 *              a
 *        b       c        d
 *      e f g    h i     j
 *
 * */
public class C03_N_aryToBinary {
    public static void main(String[] args) {
        Node a = new Node("a");
        Node b = new Node("b");
        Node c = new Node("c");
        Node d = new Node("d");
        List<Node> alist = new ArrayList<>();
        alist.add(b);alist.add(c);alist.add(d);
        a.children = alist;
        Node e = new Node("e");
        Node f = new Node("f");
        Node g = new Node("g");
        Node h = new Node("h");
        Node i = new Node("i");
        Node j = new Node("j");
        List<Node> blist = new ArrayList<>();
        blist.add(e);blist.add(f);blist.add(g);
        b.children = blist;
        List<Node> clist = new ArrayList<>();
        clist.add(h); clist.add(i);
        c.children = clist;
        List<Node> dlist = new ArrayList<>();
        dlist.add(j);
        d.children = dlist;

        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
        System.out.println(d);

        Codec codec = new Codec();
        TreeNode treeNode = codec.encode(a);

        printTree(treeNode);

        Node node_head = codec.decode(treeNode);
        System.out.println(node_head);
        for (Node n : node_head.children) {
            System.out.println(n);
        }


    }

    // 多叉树
    public static class Node {
        public String val;

        @Override
        public String toString() {
            String childreStr = "";
            if (children == null || children.size() == 0) {

            } else {
                for (Node node: children) {
                    childreStr += (node.val + ",");
                }
            }

            return "Nodea{" +
                    "val='" + val + '\'' +
                    ", children= [" + childreStr +
                    "]}";
        }

        public List<Node> children;
        public Node(String val) {
            this.val = val;
        }
        public Node(String val, List<Node> children) {
            this.val = val;
            this.children = children;
        }
    }
    // 二叉树
    public static class TreeNode{
        public String value;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(String val) {
            this.value = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val='" + value + '\'' +
                    ", left=" + (left == null ? null : left.value) +
                    ", right=" + (right == null ? null : right.value) +
                    '}';
        }
    }

    static class Codec {
        public TreeNode encode(Node root) {
            String val = root.val;
            List<Node> children = root.children;
            TreeNode head = new TreeNode(val);
            head.left = en(children);
            return head;
        }

        private TreeNode en(List<Node> children) {
            if (children == null || children.size() == 0) return null;

            TreeNode head = null; // 二叉树父节点的左叶子节点
            TreeNode cur = null;
            for (Node node : children) {
                TreeNode tnode = new TreeNode(node.val);
                if (head == null) {
                    head = tnode;
                } else {
                    cur.right = tnode;
                }
                cur = tnode;
                cur.left = en(node.children);
            }
            return head;
        }

        public Node decode(TreeNode root) {
            if (root == null ) return null;
            Node head = new Node(root.value, de(root.left));
            return head;
        }

        private List<Node> de(TreeNode treeNode) {
            if (treeNode == null) return null;
            List<Node> children = new ArrayList<>();
            TreeNode cur = treeNode;
            while (cur != null) {
                Node node = new Node(cur.value, de(cur.left));
                children.add(node);
                cur = cur.right;
            }
            return children;
        }
    }

    public static void printTree(TreeNode head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(TreeNode head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

}
